"""
134. 加油站
https://leetcode.cn/problems/integer-to-roman/description/?envType=study-plan-v2&envId=top-interview-150
"""
from typing import List


class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if sum(gas) < sum(cost): return -1
        remain = 0
        start = 0
        # 遍历所有加油站
        for i in range(len(gas)):
            # 当前剩余汽油量
            remain += gas[i] - cost[i]
            # 如果当前剩余汽油量小于0, 则从下一个加油站开始
            if remain < 0:
                # 从下一个加油站开始
                start = i + 1
                remain = 0
        return start

    def canCompleteCircuit3(self, gas: List[int], cost: List[int]) -> int:
        n = len(gas)
        i = 0
        while i < n:
            sumOfGas = 0
            sumOfCost = 0
            cnt = 0
            while cnt < n:
                j = (i + cnt) % n
                sumOfGas += gas[j]
                sumOfCost += cost[j]
                if sumOfCost > sumOfGas:
                    break
                cnt += 1
            if cnt == n:
                return i
            else:
                i = i + cnt + 1
        return -1

    def canCompleteCircuit2(self, gas: List[int], cost: List[int]) -> int:
        if sum(gas) < sum(cost):
            return -1
        if len(gas) == 1:
            return 0
        # 遍历所有加油站, 如果当前加油站的汽油大于消耗, 则从当前加油站开始遍历
        for i in range(len(gas)):
            if gas[i] >= cost[i]:
                # 从头开始遍历
                gasTemp, costTemp = gas[i:] + gas[:i], cost[i:] + cost[:i]
                gasoline = gasTemp[0]
                for j in range(1, len(gasTemp)):
                    gasoline += gasTemp[j] - costTemp[j - 1]
                    if gasoline < 0:
                        continue
                    elif j == len(gasTemp) - 1 and gasoline >= costTemp[j]:
                        return i
        return -1


if __name__ == '__main__':
    print(Solution().canCompleteCircuit(gas=[0, 0, 0, 1, 5], cost=[1, 1, 1, 1, 2]))
    # print(Solution().canCompleteCircuit(gas=[2, 3, 4], cost=[3, 4, 3]))
    # print(Solution().canCompleteCircuit(gas=[1], cost=[1]))
